{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Spiral Matrix IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #linked-list #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #链表 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: spiralMatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #螺旋矩阵 IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数：<code>m</code> 和 <code>n</code> ，表示矩阵的维数。</p>\n",
    "\n",
    "<p>另给你一个整数链表的头节点 <code>head</code> 。</p>\n",
    "\n",
    "<p>请你生成一个大小为 <code>m x n</code> 的螺旋矩阵，矩阵包含链表中的所有整数。链表中的整数从矩阵 <strong>左上角</strong> 开始、<strong>顺时针 </strong>按 <strong>螺旋</strong> 顺序填充。如果还存在剩余的空格，则用 <code>-1</code> 填充。</p>\n",
    "\n",
    "<p>返回生成的矩阵。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/05/09/ex1new.jpg\" style=\"width: 240px; height: 150px;\">\n",
    "<pre><strong>输入：</strong>m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]\n",
    "<strong>输出：</strong>[[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]\n",
    "<strong>解释：</strong>上图展示了链表中的整数在矩阵中是如何排布的。\n",
    "注意，矩阵中剩下的空格用 -1 填充。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/05/11/ex2.jpg\" style=\"width: 221px; height: 60px;\">\n",
    "<pre><strong>输入：</strong>m = 1, n = 4, head = [0,1,2]\n",
    "<strong>输出：</strong>[[0,1,2,-1]]\n",
    "<strong>解释：</strong>上图展示了链表中的整数在矩阵中是如何从左到右排布的。 \n",
    "注意，矩阵中剩下的空格用 -1 填充。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li>链表中节点数目在范围 <code>[1, m * n]</code> 内</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [spiral-matrix-iv](https://leetcode.cn/problems/spiral-matrix-iv/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [spiral-matrix-iv](https://leetcode.cn/problems/spiral-matrix-iv/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n5\\n[3,0,2,6,8,1,7,9,4,2,5,5,0]', '1\\n4\\n[0,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, R: int, C: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "\n",
    "        ans = [(rStart,cStart)]\n",
    "\n",
    "        if R * C == 1 : return ans \n",
    "\n",
    "        for k in range(1, 2 * (R + C) , 2): \n",
    "\n",
    "            for dr, dc, dk in ((0,1,k), (1,0,k), (0, -1, k+1), (-1, 0, k + 1)): \n",
    "\n",
    "                for _ in range(dk):\n",
    "\n",
    "                    rStart += dr\n",
    "                    cStart += dc\n",
    "\n",
    "\n",
    "                    if 0 <= rStart < R and 0 <= cStart < C: \n",
    "                         ans.append((rStart, cStart))\n",
    "                         if len(ans) == R * C: \n",
    "                             return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def spiralMatrixIII(self, R, C, r0, c0):\n",
    "        ans = [(r0, c0)]\n",
    "        if R * C == 1: return ans\n",
    "\n",
    "        # For walk length k = 1, 3, 5 ...\n",
    "        for k in range(1, 2*(R+C), 2):\n",
    "\n",
    "            # For direction (dr, dc) = east, south, west, north;\n",
    "            # and walk length dk...\n",
    "            for dr, dc, dk in ((0, 1, k), (1, 0, k), (0, -1, k+1), (-1, 0, k+1)):\n",
    "\n",
    "                # For each of dk units in the current direction ...\n",
    "                for _ in range(dk):\n",
    "                    # Step in that direction\n",
    "                    r0 += dr\n",
    "                    c0 += dc\n",
    "\n",
    "                    # If on the grid ...\n",
    "                    if 0 <= r0 < R and 0 <= c0 < C:\n",
    "                        ans.append((r0, c0))\n",
    "                        if len(ans) == R * C:\n",
    "                            return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        res = [(rStart, cStart)]\n",
    "        if rows * cols == 1: return res\n",
    "\n",
    "        for k in range(1, 2 * (rows + cols), 2):\n",
    "            for dr, dc, dk in ((0, 1, k), (1, 0, k), (0, -1, k + 1), (-1, 0, k + 1)):\n",
    "                for _ in range(dk):\n",
    "                    rStart += dr\n",
    "                    cStart += dc\n",
    "\n",
    "                    if 0 <= rStart < rows and 0 <= cStart < cols:\n",
    "                        res.append((rStart, cStart))\n",
    "                        if len(res) == rows * cols:\n",
    "                            return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        ans = [[rStart, cStart]]\n",
    "        if rows * cols == 1: return ans\n",
    "\n",
    "        for k in range(1, 2 * max(rows, cols), 2):\n",
    "            for dr, dc, dk in ((0, 1, k), (1, 0, k), (0, -1, k+1), (-1, 0, k+1)):\n",
    "\n",
    "                # For each of dk units in the current direction ...\n",
    "                for _ in range(dk):\n",
    "                    # Step in that direction\n",
    "                    rStart += dr\n",
    "                    cStart += dc\n",
    "\n",
    "                    # If on the grid ...\n",
    "                    if 0 <= rStart < rows and 0 <= cStart < cols:\n",
    "                        ans.append((rStart, cStart))\n",
    "                        if len(ans) == rows * cols:\n",
    "                            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def spiralMatrixIII(self, R, C, r0, c0):\n",
    "        ans = [(r0, c0)]\n",
    "        if R * C == 1: return ans\n",
    "\n",
    "        # For walk length k = 1, 3, 5 ...\n",
    "        for k in range(1, 2*max(R,C), 2):\n",
    "\n",
    "            # For direction (dr, dc) = east, south, west, north;\n",
    "            # and walk length dk...\n",
    "            for dr, dc, dk in ((0, 1, k), (1, 0, k), (0, -1, k+1), (-1, 0, k+1)):\n",
    "\n",
    "                # For each of dk units in the current direction ...\n",
    "                for _ in range(dk):\n",
    "                    # Step in that direction\n",
    "                    r0 += dr\n",
    "                    c0 += dc\n",
    "\n",
    "                    # If on the grid ...\n",
    "                    if 0 <= r0 < R and 0 <= c0 < C:\n",
    "                        ans.append((r0, c0))\n",
    "                        if len(ans) == R * C:\n",
    "                            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        i,j = rStart,cStart\n",
    "        res = [(i, j)]\n",
    "        step = 1\n",
    "        def add(i, j):\n",
    "            if i < rows and i >= 0 and j < cols and j >= 0:\n",
    "                res.append((i, j))\n",
    "        \n",
    "        while len(res) < rows * cols:\n",
    "            maxJ = j + step\n",
    "            while j < maxJ:\n",
    "                j += 1\n",
    "                add(i, j)\n",
    "            maxI = i + step\n",
    "            while i < maxI:\n",
    "                i += 1\n",
    "                add(i, j)\n",
    "            step += 1\n",
    "            minJ = j - step\n",
    "            while j > minJ:\n",
    "                j -= 1\n",
    "                add(i, j)\n",
    "\n",
    "            minI = i - step\n",
    "            while i > minI:\n",
    "                i -= 1\n",
    "                add(i, j)\n",
    "            step += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def spiralMatrixIII(self, R, C, r0, c0):\n",
    "        ans = [(r0, c0)]\n",
    "        if R * C == 1: return ans\n",
    "\n",
    "        # For walk length k = 1, 3, 5 ...\n",
    "        for k in range(1, 2*max(R,C), 2):\n",
    "\n",
    "            # For direction (dr, dc) = east, south, west, north;\n",
    "            # and walk length dk...\n",
    "            for dr, dc, dk in ((0, 1, k), (1, 0, k), (0, -1, k+1), (-1, 0, k+1)):\n",
    "\n",
    "                # For each of dk units in the current direction ...\n",
    "                for _ in range(dk):\n",
    "                    # Step in that direction\n",
    "                    r0 += dr\n",
    "                    c0 += dc\n",
    "\n",
    "                    # If on the grid ...\n",
    "                    if 0 <= r0 < R and 0 <= c0 < C:\n",
    "                        ans.append((r0, c0))\n",
    "                        if len(ans) == R * C:\n",
    "                            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        step=1\n",
    "        directions=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        cur=0\n",
    "        res=[[rStart,cStart]]\n",
    "        step_plus=0\n",
    "        cnt=1\n",
    "        while cnt<rows*cols:\n",
    "            for _ in range(step):\n",
    "                rStart+=directions[cur][0]\n",
    "                cStart+=directions[cur][1]\n",
    "                if 0<=rStart<rows and 0<=cStart<cols:\n",
    "                    res.append([rStart,cStart])\n",
    "                    cnt+=1\n",
    "            step_plus+=1\n",
    "            if step_plus%2==0:\n",
    "                step+=1\n",
    "            cur=(cur+1)%4\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOVE = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        direction = 0\n",
    "        step = 2\n",
    "        ans = [(rStart, cStart)]\n",
    "        target = rows * cols\n",
    "        while len(ans) < target:\n",
    "            dr, dc = MOVE[direction]\n",
    "            for _ in range(step >> 1):                \n",
    "                rStart += dr\n",
    "                cStart += dc\n",
    "                if -1 < rStart < rows and -1 < cStart < cols:\n",
    "                    ans.append((rStart, cStart))\n",
    "            direction = (direction + 1) % 4\n",
    "            step += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        ans = [(rStart, cStart)]\n",
    "        if rows * cols == 1: return ans\n",
    "        for k in range(1, 2 * (rows + cols), 2):\n",
    "            for dr, dc, dk in ((0, 1, k), (1, 0, k), (0, -1, k+1), (-1, 0, k+1)):\n",
    "                for _ in range(dk):\n",
    "                    rStart += dr\n",
    "                    cStart += dc\n",
    "                    if 0 <= rStart < rows and 0 <= cStart < cols:\n",
    "                        ans.append((rStart, cStart))\n",
    "                        if len(ans) == rows * cols:\n",
    "                            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, R: int, C: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "\n",
    "        ans = [(rStart,cStart)]\n",
    "\n",
    "        if R * C == 1 : return ans \n",
    "\n",
    "        for k in range(1, 2 * (R + C) , 2): \n",
    "\n",
    "            for dr, dc, dk in ((0,1,k), (1,0,k), (0, -1, k+1), (-1, 0, k + 1)): \n",
    "\n",
    "                for _ in range(dk):\n",
    "\n",
    "                    rStart += dr\n",
    "                    cStart += dc\n",
    "\n",
    "\n",
    "                    if 0 <= rStart < R and 0 <= cStart < C: \n",
    "                         ans.append((rStart, cStart))\n",
    "                         if len(ans) == R * C: \n",
    "                             return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        dirs = [[0,1], [1,0], [0,-1], [-1,0]]\n",
    "\n",
    "        res = []\n",
    "\n",
    "        n = rows * cols\n",
    "        res.append([rStart, cStart])\n",
    "        n -= 1\n",
    "        k = 1\n",
    "        ii = 0\n",
    "        i = rStart\n",
    "        j = cStart\n",
    "        while n:\n",
    "            for _ in range(2):\n",
    "                for _ in range(k):\n",
    "                    di, dj = dirs[ii]\n",
    "                    i += di\n",
    "                    j += dj\n",
    "\n",
    "                    if 0 <= i < rows and 0 <= j < cols:\n",
    "                        res.append([i, j])\n",
    "                        n -= 1\n",
    "                        if n == 0:\n",
    "                            return res\n",
    "                ii += 1\n",
    "                ii %= 4\n",
    "            k += 1\n",
    "            \n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def spiralMatrixIII(self, R, C, r0, c0):\n",
    "        ans = [(r0, c0)]\n",
    "        if R * C == 1: return ans\n",
    "\n",
    "        # For walk length k = 1, 3, 5 ...\n",
    "        for k in range(1, 2*(R+C), 2):\n",
    "\n",
    "            # For direction (dr, dc) = east, south, west, north;\n",
    "            # and walk length dk...\n",
    "            for dr, dc, dk in ((0, 1, k), (1, 0, k), (0, -1, k+1), (-1, 0, k+1)):\n",
    "\n",
    "                # For each of dk units in the current direction ...\n",
    "                for _ in range(dk):\n",
    "                    # Step in that direction\n",
    "                    r0 += dr\n",
    "                    c0 += dc\n",
    "\n",
    "                    # If on the grid ...\n",
    "                    if 0 <= r0 < R and 0 <= c0 < C:\n",
    "                        ans.append((r0, c0))\n",
    "                        if len(ans) == R * C:\n",
    "                            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        # 顺时针方向（东南西北）\n",
    "        around = [(0,1), (1,0), (0,-1), (-1, 0)]\n",
    "        # 当前四个方向的可达边界\n",
    "        left, right, top, bottom = cStart-1, cStart+1, rStart-1, rStart+1\n",
    "        # 当前的坐标x,y, 当前数字,方向指示\n",
    "        x, y, number, Dir = rStart, cStart, 1, 0\n",
    "        \n",
    "        # 开始螺旋,每循环一次会加一个元素\n",
    "        while number <= rows*cols:\n",
    "            if x>=0 and x<rows and y>=0 and y<cols:\n",
    "                res.append([x,y])\n",
    "                number += 1\n",
    "            if Dir == 0 and y==right:\n",
    "                Dir += 1\n",
    "                right += 1\n",
    "            elif Dir == 1 and x==bottom:\n",
    "                Dir += 1\n",
    "                bottom += 1\n",
    "            elif Dir == 2 and y == left:\n",
    "                Dir += 1\n",
    "                left -= 1\n",
    "            elif Dir == 3 and x==top:\n",
    "                Dir = 0 \n",
    "                top -= 1\n",
    "                \n",
    "            # 根据方向决定下一个坐标\n",
    "            x += around[Dir][0]\n",
    "            y += around[Dir][1]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        result, i, j, di, dj = [[rStart, cStart]], rStart, cStart, 1, 1\n",
    "        for r in range(1, max(i+1, j+1, rows-i, cols-j) * 2 + 1):\n",
    "            for _ in range(r):\n",
    "                0 <= (j := j + dj) < cols and 0 <= i < rows and result.append([i, j])\n",
    "            for _ in range(r):\n",
    "                0 <= (i := i + di) < rows and 0 <= j < cols and result.append([i, j])\n",
    "            di, dj = -di, -dj\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        drcs = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        ans, idx, val = [[rStart, cStart]], 0, 1\n",
    "        while len(ans) < rows * cols:\n",
    "            for _ in range(val):\n",
    "                rStart += drcs[idx][0]\n",
    "                cStart += drcs[idx][1]\n",
    "                if -1 < rStart < rows and -1 < cStart < cols:\n",
    "                    ans.append([rStart, cStart])\n",
    "                    if len(ans) == rows * cols: return ans\n",
    "            idx = (idx + 1) % 4\n",
    "            if idx % 2 == 0: val += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        ans, r, c, d, cnt, ma = [[rStart, cStart]], rStart, cStart, 0, 1, rows * cols\n",
    "        while cnt < ma:\n",
    "            if   d == 0: \n",
    "                c += 1\n",
    "                if c - cStart == rStart - r + 1: d = 1\n",
    "            elif d == 1: \n",
    "                r += 1\n",
    "                if c - cStart == r - rStart: d = 2\n",
    "            elif d == 2: \n",
    "                c -= 1\n",
    "                if cStart - c == r - rStart: d = 3\n",
    "            else       : \n",
    "                r -= 1\n",
    "                if cStart - c == rStart - r: d = 0\n",
    "            if 0 <= r < rows and 0 <= c < cols: \n",
    "                ans.append([r, c])\n",
    "                cnt += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        \n",
    "\n",
    "        n = rows * cols\n",
    "        res = [(rStart,cStart)]\n",
    "\n",
    "        i, j = rStart, cStart + 1\n",
    "\n",
    "        n -= 1\n",
    "        k = 1\n",
    "        while n:\n",
    "            while abs(i - rStart) <= k and abs(j - cStart) <= k:\n",
    "                if 0 <= i < rows and 0 <= j < cols:\n",
    "                    res.append([i, j])\n",
    "                    n -= 1\n",
    "                    if n == 0:\n",
    "                        return res\n",
    "                \n",
    "                i += 1\n",
    "            \n",
    "            i -= 1\n",
    "            j -= 1\n",
    "\n",
    "            while abs(i - rStart) <= k and abs(j - cStart) <= k:\n",
    "                if 0 <= i < rows and 0 <= j < cols:\n",
    "                    res.append([i, j])\n",
    "                    n -= 1\n",
    "                    if n == 0:\n",
    "                        return res\n",
    "                j -= 1\n",
    "            \n",
    "            j += 1\n",
    "            i -= 1\n",
    "\n",
    "            while abs(i - rStart) <= k and abs(j - cStart) <= k:\n",
    "                if 0 <= i < rows and 0 <= j < cols:\n",
    "                    res.append([i, j])\n",
    "                    n -= 1\n",
    "                    if n == 0:\n",
    "                        return res\n",
    "\n",
    "                i -= 1\n",
    "            i += 1\n",
    "            j += 1\n",
    "\n",
    "            while abs(i - rStart) <= k and abs(j - cStart) <= k:\n",
    "                if 0 <= i < rows and 0 <= j < cols:\n",
    "                    res.append([i, j])\n",
    "                    n -= 1\n",
    "                    if n == 0:\n",
    "                        return res\n",
    "                j += 1\n",
    "            \n",
    "            k += 1\n",
    "\n",
    "\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        around = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        left, right, upper, bottom = c0 - 1, c0 + 1, r0 - 1, r0 + 1\n",
    "        x, y, num, dirs = r0, c0, 1, 0\n",
    "        while num <= R * C:\n",
    "            if 0 <= x < R and 0 <= y < C:\n",
    "                res.append([x, y])\n",
    "                num += 1\n",
    "            if dirs == 0 and y == right:    ##向右到右边界\n",
    "                dirs += 1   ##向右到右边界\n",
    "                right += 1  ##右边界右移\n",
    "            elif dirs == 1 and x == bottom:  ##向下到底边界\n",
    "                dirs += 1\n",
    "                bottom += 1 ##底边界下移\n",
    "            elif dirs == 2 and y == left:   ##向左到左边界\n",
    "                dirs += 1\n",
    "                left -= 1   ##左边界左移\n",
    "            elif dirs == 3 and x == upper:\n",
    "                dirs = 0\n",
    "                upper -= 1\n",
    "            x += around[dirs][0]\n",
    "            y += around[dirs][1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        if rows == 1 and cols == 1:\n",
    "            return [[0,0]]\n",
    "        res = [[rStart,cStart]]\n",
    "        x,y = rStart,cStart\n",
    "        direct = ((0,1),(1,0),(0,-1),(-1,0)) \n",
    "        i = 1\n",
    "        dircnt = 0\n",
    "        while True:\n",
    "            for _ in range(2): \n",
    "                dx,dy = direct[dircnt%4] \n",
    "                for _ in range(i):\n",
    "                    x += dx\n",
    "                    y += dy\n",
    "                    if 0 <= x < rows and 0 <= y < cols:\n",
    "                        res.append([x,y])\n",
    "                        if len(res) == rows*cols:\n",
    "                            return res\n",
    "                dircnt += 1 \n",
    "            i += 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        res = [[rStart, cStart]]\n",
    "        d = cnt = 0\n",
    "        i, j = rStart, cStart\n",
    "        direct = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        while len(res) < rows * cols:\n",
    "            for _ in range(cnt // 2 + 1):\n",
    "                i += direct[d][0]\n",
    "                j += direct[d][1]\n",
    "                if 0 <= i < rows and 0 <= j < cols and len(res) < rows * cols:\n",
    "                    res.append([i, j])\n",
    "            cnt += 1\n",
    "            d = (d + 1) % 4\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        result = []\n",
    "        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        direction = 0\n",
    "        row, col = rStart, cStart\n",
    "        step = 1\n",
    "\n",
    "        while len(result) < rows * cols:\n",
    "            for _ in range(2):\n",
    "                dx, dy = directions[direction]\n",
    "                for _ in range(step):\n",
    "                    if 0 <= row < rows and 0 <= col < cols:\n",
    "                        result.append([row, col])\n",
    "                    row += dx\n",
    "                    col += dy\n",
    "                direction = (direction + 1) % 4\n",
    "            step += 1\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 模拟\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        d = 0\n",
    "        x, y = rStart, cStart\n",
    "        m, n = rows, cols\n",
    "        ans = [[x, y]]\n",
    "        step = 1\n",
    "        while len(ans) < m * n:\n",
    "            for z in [d, d + 1]:\n",
    "                a, b = direction[z]\n",
    "                for _ in range(step):\n",
    "                    x += a\n",
    "                    y += b\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        ans.append([x, y])\n",
    "                        \n",
    "            d = (d + 2) % 4\n",
    "            step += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        step = 1\n",
    "        directs = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        res = [[rStart, cStart]]\n",
    "        r, c = rStart, cStart\n",
    "\n",
    "        while len(res) < rows * cols:\n",
    "            for d in directs:\n",
    "                if d in [[0, 1], [1, 0]]:\n",
    "                    for _ in range(step):\n",
    "                        r, c = r + d[0], c + d[1]\n",
    "                        if 0 <= r < rows and 0 <= c < cols:\n",
    "                            res.append([r, c])\n",
    "                else:\n",
    "                    for _ in range(step + 1):\n",
    "                        r, c = r + d[0], c + d[1]\n",
    "                        if 0 <= r < rows and 0 <= c < cols:\n",
    "                            res.append([r, c])\n",
    "            step += 2\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        ans = [[rStart,cStart]]\n",
    "        if rows*cols == 1:\n",
    "            return ans\n",
    "        dirs = ((0,1),(1,0),(0,-1),(-1,0))\n",
    "        i,d = 1,0\n",
    "        x,y = ans[0]\n",
    "        while True:\n",
    "            for _ in range(2):\n",
    "                dx,dy = dirs[d]\n",
    "                for _ in range(i):\n",
    "                    x += dx\n",
    "                    y += dy\n",
    "                    if 0 <= x < rows and 0 <= y < cols:\n",
    "                        ans.append([x,y])\n",
    "                        if len(ans) == rows*cols:\n",
    "                            return ans\n",
    "                d += 1\n",
    "                d %= 4\n",
    "            i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        m, n = rows, cols\n",
    "        ans = [[rStart, cStart]]\n",
    "        d = [(0, 1), (1, 0), (0, -1),(-1, 0)]\n",
    "        i, j = rStart, cStart\n",
    "        k = 0\n",
    "        while len(ans) < m * n:\n",
    "            # print(k, i, j, ans)\n",
    "            \n",
    "            for _ in range(k//2 + 1):\n",
    "                i, j = i + d[k%4][0], j + d[k%4][1]\n",
    "                if 0<=i<m and 0<=j<n:\n",
    "                    ans.append([i, j])\n",
    "            k += 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 模拟\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        d = 0\n",
    "        x, y = rStart, cStart\n",
    "        m, n = rows, cols\n",
    "        ans = [[x, y]]\n",
    "        step = 1\n",
    "        while len(ans) < m * n:\n",
    "            for z in [d, d + 1]:\n",
    "                a, b = direction[z]\n",
    "                for _ in range(step):\n",
    "                    x += a\n",
    "                    y += b\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        ans.append([x, y])\n",
    "\n",
    "            d = (d + 2) % 4\n",
    "            step += 1\n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        ans = [[rStart, cStart]]\n",
    "        i = rStart\n",
    "        j = cStart\n",
    "        length = 1\n",
    "        changeTimes = 0\n",
    "        dir = 'right'\n",
    "        while len(ans) != rows * cols:\n",
    "            if dir == 'right':\n",
    "                for a in range(length):\n",
    "                    j += 1\n",
    "                    if 0 <= i < rows and 0 <= j < cols:\n",
    "                        ans.append([i, j])\n",
    "                dir = 'down'\n",
    "\n",
    "            elif dir == 'down':\n",
    "                for a in range(length):\n",
    "                    i += 1\n",
    "                    if 0 <= i < rows and 0 <= j < cols:\n",
    "                        ans.append([i, j])\n",
    "                dir = 'left'\n",
    "\n",
    "            elif dir == 'left':\n",
    "                for a in range(length):\n",
    "                    j -= 1\n",
    "                    if 0 <= i < rows and 0 <= j < cols:\n",
    "                        ans.append([i, j])\n",
    "                dir = 'top'\n",
    "\n",
    "            elif dir == 'top':\n",
    "                for a in range(length):\n",
    "                    i -= 1\n",
    "                    if 0 <= i < rows and 0 <= j < cols:\n",
    "                        ans.append([i, j])\n",
    "                dir = 'right'\n",
    "\n",
    "            changeTimes += 1\n",
    "            if changeTimes == 2:\n",
    "                changeTimes = 0\n",
    "                length += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        if rows == 1 and cols == 1:\n",
    "            return [[0,0]]\n",
    "        res = [[rStart,cStart]]\n",
    "        x,y = rStart,cStart\n",
    "        direct = ((0,1),(1,0),(0,-1),(-1,0)) \n",
    "        i = 1\n",
    "        dircnt = 0\n",
    "        while True:\n",
    "            for _ in range(2): \n",
    "                dx,dy = direct[dircnt%4] \n",
    "                for _ in range(i):\n",
    "                    x += dx\n",
    "                    y += dy\n",
    "                    if 0 <= x < rows and 0 <= y < cols:\n",
    "                        res.append([x,y])\n",
    "                        if len(res) == rows*cols:\n",
    "                            return res\n",
    "                dircnt += 1 \n",
    "            i += 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def spiralMatrixIII(self, rows: int, cols: int, r1: int, r2: int) -> List[List[int]]:\n",
    "        nn=rows*cols\n",
    "        def g(i,j):\n",
    "           return 0<=i<rows and 0<=j<cols \n",
    "        q=Counter([(r1-1,r2-1)])\n",
    "        q[(r1,r2+1)]+=1\n",
    "        q[(r1+1,r2+1)]+=1\n",
    "        q[(r1+1,r2-1)]+=1\n",
    "        k,u=0,0\n",
    "        ans=[]\n",
    "        i,j=r1,r2\n",
    "        while 1:\n",
    "         for a,b in [[0,1],[1,0],[0,-1],[-1,0]]:\n",
    "           while (i,j) not in q:\n",
    "               \n",
    "               if u==nn:\n",
    "                   return  ans\n",
    "               if g(i,j):\n",
    "                  u+=1 \n",
    "                  ans.append([i,j]) \n",
    "               i+=a\n",
    "               j+=b\n",
    "           if g(i,j):\n",
    "                  u+=1  \n",
    "                  ans.append([i,j])    \n",
    "           q[(i,j)]-=1\n",
    "               \n",
    "           if k==0:\n",
    "               q[(i-1,j+1)]+=1\n",
    "               i+=1\n",
    "           elif k==1:\n",
    "               q[(i+1,j+1)]+=1\n",
    "               j-=1\n",
    "           elif k==2:\n",
    "               q[(i+1,j-1)]+=1\n",
    "               i-=1\n",
    "           elif k==3:\n",
    "               q[(i-1,j-1)]+=1\n",
    "               j+=1\n",
    "           k=(k+1)%4    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        r, c = rStart, cStart\n",
    "        \n",
    "        steps = 1\n",
    "        while len(res) < rows * cols:\n",
    "            for _ in range(steps):\n",
    "                if 0 <= r < rows and 0 <= c < cols:\n",
    "                    res.append([r, c])\n",
    "                c += 1\n",
    "            \n",
    "            for _ in range(steps):\n",
    "                if 0 <= r < rows and 0 <= c < cols:\n",
    "                    res.append([r, c])\n",
    "                r += 1\n",
    "            \n",
    "            steps += 1\n",
    "            \n",
    "            for _ in range(steps):\n",
    "                if 0 <= r < rows and 0 <= c < cols:\n",
    "                    res.append([r, c])\n",
    "                c -= 1\n",
    "            \n",
    "            for _ in range(steps):\n",
    "                if 0 <= r < rows and 0 <= c < cols:\n",
    "                    res.append([r, c])\n",
    "                r -= 1\n",
    "            \n",
    "            steps += 1\n",
    "        \n",
    "        return res[:rows * cols]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        \n",
    "        # 怎么确定方向，面朝东面开始，怎么确定起点\n",
    "        res = []\n",
    "        around = [(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        left,right,upper,bottom = cStart -1,cStart +1,rStart-1,rStart+1\n",
    "        x,y,num,direct=rStart,cStart,1,0\n",
    "        while num <= rows * cols:\n",
    "            if x >=0 and x < rows and y >=0 and y < cols:\n",
    "                res.append([x,y])\n",
    "                num += 1\n",
    "            if direct == 0 and y ==right:\n",
    "                direct += 1\n",
    "                right += 1\n",
    "            elif direct == 1 and x == bottom:\n",
    "                direct += 1\n",
    "                bottom += 1\n",
    "            elif direct == 2 and x == left:\n",
    "                direct += 1\n",
    "                left -= 1\n",
    "            elif direct == 3 and x == upper:\n",
    "                direct = 0\n",
    "                upper -= 1\n",
    "            x += around[direct][0]\n",
    "            y += around[direct][1]\n",
    "        return res\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        around = [(0, 1), (1, 0), (0, -1), (-1, 0)]  ##顺时针方向\n",
    "        Left, Right, Upper, Bottom = c0 - 1, c0 + 1, r0 - 1, r0 + 1  ##四个方向的边界\n",
    "        x, y, num, Dir = r0, c0, 1, 0  ##(x, y)为当前节点，num为当前查找的数字，Dir为当前的方向\n",
    "        while num <= R * C:\n",
    "            if x >= 0 and x < R and y >= 0 and y < C:  ##(x, y)在矩阵中\n",
    "                res.append([x, y])\n",
    "                num += 1\n",
    "            if Dir == 0 and y == Right:  ##向右到右边界\n",
    "                Dir += 1  ##调转方向向下\n",
    "                Right += 1  ##右边界右移\n",
    "            elif Dir == 1 and x == Bottom:  ##向下到底边界\n",
    "                Dir += 1\n",
    "                Bottom += 1  ##底边界下移\n",
    "            elif Dir == 2 and y == Left:  ##向左到左边界\n",
    "                Dir += 1\n",
    "                Left -= 1  ##左边界左移\n",
    "            elif Dir == 3 and x == Upper:  ##向上到上边界\n",
    "                Dir = 0\n",
    "                Upper -= 1  ##上边界上移\n",
    "            x += around[Dir][0]\n",
    "            y += around[Dir][1]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        if rows == 1 and cols == 1:\n",
    "            return [[0,0]]\n",
    "        res = [[rStart,cStart]]\n",
    "        x,y = rStart,cStart\n",
    "        direct = ((0,1),(1,0),(0,-1),(-1,0)) \n",
    "        i = 1\n",
    "        dircnt = 0\n",
    "        while True:\n",
    "            for _ in range(2): \n",
    "                dx,dy = direct[dircnt%4] \n",
    "                for _ in range(i):\n",
    "                    x += dx\n",
    "                    y += dy\n",
    "                    if 0 <= x < rows and 0 <= y < cols:\n",
    "                        res.append([x,y])\n",
    "                        if len(res) == rows*cols:\n",
    "                            return res\n",
    "                dircnt += 1 \n",
    "            i += 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        ans, r, c, d, cnt, ma = [[rStart, cStart]], rStart, cStart, 0, 1, rows * cols\n",
    "        while cnt < ma:\n",
    "            if   d == 0: \n",
    "                c += 1\n",
    "                if c - cStart == rStart - r + 1: d = 1\n",
    "            elif d == 1: \n",
    "                r += 1\n",
    "                if c - cStart == r - rStart: d = 2\n",
    "            elif d == 2: \n",
    "                c -= 1\n",
    "                if cStart - c == r - rStart: d = 3\n",
    "            else       : \n",
    "                r -= 1\n",
    "                if cStart - c == rStart - r: d = 0\n",
    "            if 0 <= r < rows and 0 <= c < cols: \n",
    "                ans.append([r, c])\n",
    "                cnt += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\r\n",
    "        res = []\r\n",
    "        \r\n",
    "        target = rows * cols\r\n",
    "        row, col = rStart, cStart\r\n",
    "        step = 0\r\n",
    "        while True:\r\n",
    "            step += 1\r\n",
    "            for i in range(col, col+step):\r\n",
    "                if 0 <= i < cols and 0 <= row < rows:\r\n",
    "                    res.append([row, i])\r\n",
    "                    if len(res) == target:\r\n",
    "                        return res\r\n",
    "            col += step\r\n",
    "\r\n",
    "            for i in range(row, row+step):\r\n",
    "                if 0 <= i < rows and 0 <= col < cols:\r\n",
    "                    res.append([i, col])\r\n",
    "                    if len(res) == target:\r\n",
    "                        return res\r\n",
    "            row += step\r\n",
    "            \r\n",
    "            step += 1\r\n",
    "            for i in range(col, col-step, -1):\r\n",
    "                if 0 <= i < cols and 0 <= row < rows:\r\n",
    "                    res.append([row, i])\r\n",
    "                    if len(res) == target:\r\n",
    "                        return res\r\n",
    "            col -= step\r\n",
    "\r\n",
    "            for i in range(row, row-step, -1):\r\n",
    "                if 0 <= i < rows and 0 <= col < cols:\r\n",
    "                    res.append([i, col])\r\n",
    "                    if len(res) == target:\r\n",
    "                        return res\r\n",
    "            row -= step\r\n",
    "                    \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        step=1\n",
    "        directions=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        cur=0\n",
    "        res=[[rStart,cStart]]\n",
    "        step_plus=0\n",
    "        cnt=1\n",
    "        while cnt<rows*cols:\n",
    "            for _ in range(step):\n",
    "                rStart+=directions[cur][0]\n",
    "                cStart+=directions[cur][1]\n",
    "            \n",
    "                if 0<=rStart<rows and 0<=cStart<cols:\n",
    "                    res.append([rStart,cStart])\n",
    "                    cnt+=1\n",
    "            step_plus+=1\n",
    "            if step_plus%2==0:\n",
    "                step+=1\n",
    "            cur=(cur+1)%4\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        around = [(0, 1), (1, 0), (0, -1), (-1, 0)]  ##顺时针方向\n",
    "        Left, Right, Upper, Bottom = c0 - 1, c0 + 1, r0 - 1, r0 + 1  ##四个方向的边界\n",
    "        x, y, num, Dir = r0, c0, 1, 0  ##(x, y)为当前节点，num为当前查找的数字，Dir为当前的方向\n",
    "        while num <= R * C:\n",
    "            if x >= 0 and x < R and y >= 0 and y < C:  ##(x, y)在矩阵中\n",
    "                res.append([x, y])\n",
    "                num += 1\n",
    "            if Dir == 0 and y == Right:  ##向右到右边界\n",
    "                Dir += 1  ##调转方向向下\n",
    "                Right += 1  ##右边界右移\n",
    "            elif Dir == 1 and x == Bottom:  ##向下到底边界\n",
    "                Dir += 1\n",
    "                Bottom += 1  ##底边界下移\n",
    "            elif Dir == 2 and y == Left:  ##向左到左边界\n",
    "                Dir += 1\n",
    "                Left -= 1  ##左边界左移\n",
    "            elif Dir == 3 and x == Upper:  ##向上到上边界\n",
    "                Dir = 0\n",
    "                Upper -= 1  ##上边界上移\n",
    "            x += around[Dir][0]\n",
    "            y += around[Dir][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, m: int, n: int, x: int, y: int) -> List[List[int]]:\n",
    "        \n",
    "        ind = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        ans = [[x, y]]\n",
    "        d = 0\n",
    "        step = 1\n",
    "        while len(ans)<m*n:\n",
    "            for _ in range(step):\n",
    "                x += ind[d][0]\n",
    "                y += ind[d][1]\n",
    "                if 0<=x<m and 0<=y<n:\n",
    "                    ans.append([x, y])\n",
    "            d = (d+1)%4\n",
    "            for _ in range(step):\n",
    "                x += ind[d][0]\n",
    "                y += ind[d][1]\n",
    "                if 0<=x<m and 0<=y<n:\n",
    "                    ans.append([x, y])\n",
    "            d = (d+1)%4\n",
    "            step += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        tot = 1 \n",
    "        dx = [0, 1, 0, -1]\n",
    "        dy = [1, 0, -1, 0]\n",
    "        d = 0\n",
    "        ans = [[rStart, cStart]]\n",
    "        Q = deque([(0, 1, rStart, cStart)])\n",
    "        while tot < rows * cols:\n",
    "            d, l, x, y = Q.popleft() \n",
    "            for i in range(l):\n",
    "                x, y = x + dx[d], y + dy[d]\n",
    "                if 0<=x<rows and 0<=y<cols:\n",
    "                    ans.append([x,y])\n",
    "                    tot += 1\n",
    "            d = (d+1) % 4\n",
    "            for i in range(l):\n",
    "                x, y = x + dx[d], y + dy[d]\n",
    "                if 0<=x<rows and 0<=y<cols:\n",
    "                    ans.append([x,y])\n",
    "                    tot += 1 \n",
    "            d = (d+1) % 4 \n",
    "            Q.append((d, l + 1, x, y))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        ans, r, c, d, cnt, ma = [[rStart, cStart]], rStart, cStart, 0, 1, rows * cols\n",
    "        while cnt < ma:\n",
    "            if   d == 0: \n",
    "                c += 1\n",
    "                if c - cStart == rStart - r + 1: d = 1\n",
    "            elif d == 1: \n",
    "                r += 1\n",
    "                if c - cStart == r - rStart: d = 2\n",
    "            elif d == 2: \n",
    "                c -= 1\n",
    "                if cStart - c == r - rStart: d = 3\n",
    "            else       : \n",
    "                r -= 1\n",
    "                if cStart - c == rStart - r: d = 0\n",
    "            if 0 <= r < rows and 0 <= c < cols: \n",
    "                ans.append([r, c])\n",
    "                cnt += 1\n",
    "            #print(r, c, d, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        \n",
    "        nums = rows * cols\n",
    "        cur = [rStart, cStart]\n",
    "        ans = [[rStart, cStart]]\n",
    "\n",
    "        dire = ['right', 'buttom', 'left', 'top']\n",
    "\n",
    "        steps = 1\n",
    "        index = 0\n",
    "\n",
    "        while len(ans) < nums:\n",
    "            direction = dire[index]\n",
    "            if direction == 'right':\n",
    "                for _ in range(int(steps)):\n",
    "                    cur[1] += 1\n",
    "                    if cur[0] >= rows or cur[0] < 0 or cur[1] >= cols or cur[1] < 0: continue\n",
    "                    ans.append([cur[0],cur[1]])\n",
    "            elif direction == 'left':\n",
    "                for _ in range(int(steps)):\n",
    "                    cur[1] -= 1\n",
    "                    if cur[0] >= rows or cur[0] < 0 or cur[1] >= cols or cur[1] < 0: continue\n",
    "                    ans.append([cur[0],cur[1]])\n",
    "            elif direction == 'buttom':\n",
    "                for _ in range(int(steps)):\n",
    "                    cur[0] += 1\n",
    "                    if cur[0] >= rows or cur[0] < 0 or cur[1] >= cols or cur[1] < 0: continue\n",
    "                    ans.append([cur[0],cur[1]])\n",
    "            elif direction == 'top':\n",
    "                for _ in range(int(steps)):\n",
    "                    cur[0] -= 1\n",
    "                    if cur[0] >= rows or cur[0] < 0 or cur[1] >= cols or cur[1] < 0: continue\n",
    "                    ans.append([cur[0],cur[1]])\n",
    "            steps += 0.5\n",
    "            index += 1\n",
    "            if index == 4:index = 0\n",
    "        return ans                   \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\r\n",
    "        ans = [[rStart, cStart]]\r\n",
    "        r, c = rStart, cStart\r\n",
    "        step = 1\r\n",
    "        while len(ans) < rows * cols:\r\n",
    "            for _ in range(step):\r\n",
    "                c += 1\r\n",
    "                if 0 <= r < rows and 0 <= c < cols:\r\n",
    "                    ans.append([r, c])\r\n",
    "            for _ in range(step):\r\n",
    "                r += 1\r\n",
    "                if 0 <= r < rows and 0 <= c < cols:\r\n",
    "                    ans.append([r, c])\r\n",
    "            step += 1\r\n",
    "            for _ in range(step):\r\n",
    "                c -= 1\r\n",
    "                if 0 <= r < rows and 0 <= c < cols:\r\n",
    "                    ans.append([r, c])\r\n",
    "            for _ in range(step):\r\n",
    "                r -= 1\r\n",
    "                if 0 <= r < rows and 0 <= c < cols:\r\n",
    "                    ans.append([r, c])\r\n",
    "            step += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\r\n",
    "        res = []\r\n",
    "        \r\n",
    "        target = rows * cols\r\n",
    "        row, col = rStart, cStart\r\n",
    "        step = 0\r\n",
    "        while True:\r\n",
    "            step += 1\r\n",
    "            for i in range(col, col+step):\r\n",
    "                if 0 <= i < cols and 0 <= row < rows:\r\n",
    "                    res.append([row, i])\r\n",
    "                    if len(res) == target:\r\n",
    "                        return res\r\n",
    "            col += step\r\n",
    "\r\n",
    "            for i in range(row, row+step):\r\n",
    "                if 0 <= i < rows and 0 <= col < cols:\r\n",
    "                    res.append([i, col])\r\n",
    "                    if len(res) == target:\r\n",
    "                        return res\r\n",
    "            row += step\r\n",
    "            \r\n",
    "            step += 1\r\n",
    "            for i in range(col, col-step, -1):\r\n",
    "                if 0 <= i < cols and 0 <= row < rows:\r\n",
    "                    res.append([row, i])\r\n",
    "                    if len(res) == target:\r\n",
    "                        return res\r\n",
    "            col -= step\r\n",
    "\r\n",
    "            for i in range(row, row-step, -1):\r\n",
    "                if 0 <= i < rows and 0 <= col < cols:\r\n",
    "                    res.append([i, col])\r\n",
    "                    if len(res) == target:\r\n",
    "                        return res\r\n",
    "            row -= step\r\n",
    "                    \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        ans, r, c, d, cnt, ma = [[rStart, cStart]], rStart, cStart, 0, 1, rows * cols\n",
    "        while cnt < ma:\n",
    "            if   d == 0: \n",
    "                c += 1\n",
    "                if c - cStart == rStart - r + 1: d = 1\n",
    "            elif d == 1: \n",
    "                r += 1\n",
    "                if c - cStart == r - rStart: d = 2\n",
    "            elif d == 2: \n",
    "                c -= 1\n",
    "                if cStart - c == r - rStart: d = 3\n",
    "            else       : \n",
    "                r -= 1\n",
    "                if cStart - c == rStart - r: d = 0\n",
    "            if 0 <= r < rows and 0 <= c < cols: \n",
    "                ans.append([r, c])\n",
    "                cnt += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def spiralMatrixIII(self, rows: int, cols: int, r1: int, r2: int) -> List[List[int]]:\n",
    "        nn=rows*cols\n",
    "        def g(i,j):\n",
    "           return 0<=i<rows and 0<=j<cols \n",
    "        q=Counter([(r1-1,r2-1)])\n",
    "        q[(r1,r2+1)]+=1\n",
    "        q[(r1+1,r2+1)]+=1\n",
    "        q[(r1+1,r2-1)]+=1\n",
    "        k,u=0,0\n",
    "        ans=[]\n",
    "        i,j=r1,r2\n",
    "        while 1:\n",
    "         for a,b in [[0,1],[1,0],[0,-1],[-1,0]]:\n",
    "           while (i,j) not in q:\n",
    "               u+=1\n",
    "               if len(ans)==nn:\n",
    "                   return  ans\n",
    "               if g(i,j):\n",
    "                  ans.append([i,j]) \n",
    "               i+=a\n",
    "               j+=b\n",
    "           if g(i,j):\n",
    "                  ans.append([i,j])    \n",
    "           q[(i,j)]-=1\n",
    "           u+=1    \n",
    "           if k==0:\n",
    "               q[(i-1,j+1)]+=1\n",
    "               i+=1\n",
    "           elif k==1:\n",
    "               q[(i+1,j+1)]+=1\n",
    "               j-=1\n",
    "           elif k==2:\n",
    "               q[(i+1,j-1)]+=1\n",
    "               i-=1\n",
    "           elif k==3:\n",
    "               q[(i-1,j-1)]+=1\n",
    "               j+=1\n",
    "           k=(k+1)%4    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\r\n",
    "        res = []\r\n",
    "        \r\n",
    "        target = rows * cols\r\n",
    "        row, col = rStart, cStart\r\n",
    "        cnt = 0\r\n",
    "        step = 0\r\n",
    "        while True:\r\n",
    "            step += 1\r\n",
    "            for i in range(col, col+step):\r\n",
    "                if 0 <= i < cols and 0 <= row < rows:\r\n",
    "                    res.append([row, i])\r\n",
    "                    cnt += 1\r\n",
    "                    if cnt == target:\r\n",
    "                        return res\r\n",
    "            col += step\r\n",
    "\r\n",
    "            for i in range(row, row+step):\r\n",
    "                if 0 <= i < rows and 0 <= col < cols:\r\n",
    "                    res.append([i, col])\r\n",
    "                    cnt += 1\r\n",
    "                    if cnt == target:\r\n",
    "                        return res\r\n",
    "            row += step\r\n",
    "            \r\n",
    "            step += 1\r\n",
    "            for i in range(col, col-step, -1):\r\n",
    "                if 0 <= i < cols and 0 <= row < rows:\r\n",
    "                    res.append([row, i])\r\n",
    "                    cnt += 1\r\n",
    "                    if cnt == target:\r\n",
    "                        return res\r\n",
    "            col -= step\r\n",
    "\r\n",
    "            for i in range(row, row-step, -1):\r\n",
    "                if 0 <= i < rows and 0 <= col < cols:\r\n",
    "                    res.append([i, col])\r\n",
    "                    cnt += 1\r\n",
    "                    if cnt == target:\r\n",
    "                        return res\r\n",
    "            row -= step\r\n",
    "                    \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        ans, r, c, d, cnt, ma = [[rStart, cStart]], rStart, cStart, 0, 1, rows * cols\n",
    "        while cnt < ma:\n",
    "            if   d == 0: \n",
    "                c += 1\n",
    "                if c - cStart == rStart - r + 1: d = 1\n",
    "            elif d == 1: \n",
    "                r += 1\n",
    "                if c - cStart == r - rStart: d = 2\n",
    "            elif d == 2: \n",
    "                c -= 1\n",
    "                if cStart - c == r - rStart: d = 3\n",
    "            else       : \n",
    "                r -= 1\n",
    "                if cStart - c == rStart - r: d = 0\n",
    "            if 0 <= r < rows and 0 <= c < cols: \n",
    "                ans.append([r, c])\n",
    "                cnt += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        # moni\n",
    "        Dir = [(0,1),(1,0),(0,-1),(-1,0)] #右、下、左、上\n",
    "        dir = 0 #方向\n",
    "        x,y = rStart,cStart\n",
    "        num = 1\n",
    "        ans = [[x,y]]\n",
    "        Left, Right, Upper, Bottom = cStart- 1, cStart + 1, rStart - 1,rStart+ 1  ##四个方向的边界\n",
    "        ##(x, y)为当前节点，num为当前查找的数字，Dir为当前的方向\n",
    "        while num<rows*cols:\n",
    "            # print(x,y)\n",
    "            if dir == 0 and y == Right:##向右到右边界\n",
    "                dir += 1\n",
    "                Right += 1 ###右边界右移\n",
    "            elif dir == 1 and x == Bottom:##向下到底边界\n",
    "                dir += 1\n",
    "                Bottom += 1\n",
    "            elif dir == 2 and y == Left:##向左到左边界\n",
    "                dir += 1\n",
    "                Left -= 1\n",
    "            elif dir == 3 and x == Upper:##向上到上边界\n",
    "                dir = 0 \n",
    "                Upper -= 1\n",
    "            x += Dir[dir][0]\n",
    "            y += Dir[dir][1]\n",
    "            if 0<= x < rows and 0<= y<cols:\n",
    "                ans.append([x,y])\n",
    "                num += 1\n",
    "        return ans\n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        directions = [(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        left, right, upper, bottom = cStart - 1, cStart + 1, rStart - 1, rStart + 1\n",
    "        x, y, num, direction = rStart, cStart, 1, 0\n",
    "\n",
    "        while num <= rows * cols:\n",
    "            if x >= 0 and x < rows and y >= 0 and y < cols:\n",
    "                res.append([x, y])\n",
    "                num += 1\n",
    "            if direction == 0 and y == right:\n",
    "                direction += 1\n",
    "                right += 1\n",
    "            elif direction == 1 and x == bottom:\n",
    "                direction += 1\n",
    "                bottom += 1\n",
    "            elif direction == 2 and y == left:\n",
    "                direction += 1\n",
    "                left -= 1\n",
    "            elif direction == 3 and x == upper:\n",
    "                direction = 0\n",
    "                upper -= 1\n",
    "            x += directions[direction][0]\n",
    "            y += directions[direction][1]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        i, j = rStart, cStart\n",
    "        res = [[i,j]]\n",
    "        dirs = [(0,1), (1,0), (0,-1), (-1,0)]\n",
    "        index, steps = 0, 1\n",
    "        while len(res) < rows * cols:\n",
    "            di, dj = dirs[index]\n",
    "            for _ in range(steps):\n",
    "                i += di\n",
    "                j += dj\n",
    "                if 0 <= i < rows and 0 <= j < cols:\n",
    "                    res.append([i,j])\n",
    "            index = (index + 1) % 4\n",
    "            \n",
    "            di, dj = dirs[index]\n",
    "            for _ in range(steps):\n",
    "                i += di\n",
    "                j += dj\n",
    "                if 0 <= i < rows and 0 <= j < cols:\n",
    "                    res.append([i,j])\n",
    "            index = (index + 1) % 4\n",
    "            \n",
    "            steps += 1\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\n",
    "        r=rStart\n",
    "        c=cStart\n",
    "        ans=[[r,c]]\n",
    "        cnt=rows*cols-1\n",
    "        step=2\n",
    "        while cnt>0:\n",
    "            c+=1\n",
    "            if check(rows,cols,r,c):\n",
    "                ans.append([r,c])\n",
    "                cnt-=1\n",
    "            for i in range(0,step-1):\n",
    "                r+=1\n",
    "                if check(rows,cols,r,c):\n",
    "                    ans.append([r,c])\n",
    "                    cnt-=1\n",
    "            if cnt<=0:break\n",
    "            for i in range(0,step):\n",
    "                c-=1\n",
    "                if check(rows,cols,r,c):\n",
    "                    ans.append([r,c])\n",
    "                    cnt-=1\n",
    "            if cnt<=0:break\n",
    "            for i in range(0,step):\n",
    "                r-=1\n",
    "                if check(rows,cols,r,c):\n",
    "                    ans.append([r,c])\n",
    "                    cnt-=1\n",
    "            if cnt<=0:break\n",
    "            for i in range(0,step):\n",
    "                c+=1\n",
    "                if check(rows,cols,r,c):\n",
    "                    ans.append([r,c])\n",
    "                    cnt-=1\n",
    "            step+=2\n",
    "        return ans\n",
    "\n",
    "def check(rows,cols,r,c):\n",
    "    if r<0 or r>=rows:return False\n",
    "    if c<0 or c>=cols:return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:\r\n",
    "        # vis=set((rStart,cStart))\r\n",
    "        ret=[[rStart,cStart]]\r\n",
    "        dirs=[\r\n",
    "            [0,1],\r\n",
    "            [1,0],\r\n",
    "            [0,-1],\r\n",
    "            [-1,0]\r\n",
    "        ]\r\n",
    "        d=0\r\n",
    "        r,c=rStart,cStart\r\n",
    "        total=rows*cols\r\n",
    "        if total==1:\r\n",
    "            return ret\r\n",
    "        steps=1\r\n",
    "        while True:\r\n",
    "            for i in range(2):\r\n",
    "                for _ in range(steps):\r\n",
    "                    r,c=r+dirs[d][0],c+dirs[d][1]\r\n",
    "                    if 0<=r<rows and 0<=c<cols:\r\n",
    "                        ret.append([r,c])\r\n",
    "                        if len(ret)==total:\r\n",
    "                            return ret\r\n",
    "                d=(d+1)%4\r\n",
    "            steps+=1\r\n",
    "        # return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "DIRECTION = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        row = 0\n",
    "        col = 0\n",
    "        cur = 0\n",
    "        while head:\n",
    "            ans[row][col] = head.val\n",
    "            head = head.next\n",
    "            dr, dc = DIRECTION[cur]\n",
    "            if not (-1 < row + dr < m and -1 < col + dc < n and ans[row + dr][col + dc] == -1):\n",
    "                cur = (cur + 1) % 4\n",
    "                dr, dc = DIRECTION[cur]\n",
    "            row += dr\n",
    "            col += dc\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        i = j = di = 0\n",
    "        while head:\n",
    "            ans[i][j] = head.val\n",
    "            head = head.next\n",
    "            dx, dy = DIRS[di]\n",
    "            if not (0 <= i + dx < m and 0 <= j + dy < n and ans[i + dx][j + dy] == -1) :\n",
    "                di = (di + 1) % 4\n",
    "                dx, dy = DIRS[di]\n",
    "            i += dx\n",
    "            j += dy\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        i = j = di = 0\n",
    "        while head:\n",
    "            ans[i][j] = head.val\n",
    "            head = head.next\n",
    "            dx, dy = DIRS[di]\n",
    "            if not (0 <= i + dx < m and 0 <= j + dy < n and ans[i + dx][j + dy] == -1):\n",
    "                di = (di + 1) % 4\n",
    "                dx, dy = DIRS[di]\n",
    "            i += dx\n",
    "            j += dy\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        dirs = [(0,1), (1,0), (0,-1), (-1,0)]\n",
    "        row, col, dirIdx = 0, 0, 0\n",
    "        while head:\n",
    "            ans[row][col] = head.val\n",
    "            head = head.next\n",
    "            dx, dy = dirs[dirIdx]\n",
    "            if not (0 <= row + dx < m and 0 <= col + dy < n and ans[row+dx][col+dy] == -1):\n",
    "                dirIdx = (dirIdx + 1) % 4\n",
    "                dx, dy = dirs[dirIdx]\n",
    "            row += dx\n",
    "            col += dy\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        i= j = di =0\n",
    "        while head:\n",
    "            ans[i][j] = head.val\n",
    "            head = head.next\n",
    "            dx, dy = DIRS[di]\n",
    "            if not (0 <= i+dx < m and 0 <= j + dy < n and ans[i + dx][j + dy] == -1):\n",
    "                di = (di + 1)%4\n",
    "                dx, dy = DIRS[di]\n",
    "            i+=dx\n",
    "            j+=dy\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        i = j = di = 0\n",
    "        while head:\n",
    "            ans[i][j] = head.val\n",
    "            head = head.next\n",
    "            dx, dy = DIRS[di]\n",
    "            if not (0 <= i + dx < m and 0 <= j + dy < n and ans[i+dx][j+dy] == -1):\n",
    "                di = (di + 1) % 4\n",
    "                dx, dy = DIRS[di]\n",
    "            i += dx\n",
    "            j += dy\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        i = j = di = 0\n",
    "        while head:\n",
    "            ans[i][j] = head.val\n",
    "            head = head.next\n",
    "            dx, dy = DIRS[di]\n",
    "            if not (0 <= i + dx < m and 0 <= j + dy < n and ans[i + dx][j + dy] == -1):\n",
    "                di = (di + 1) % 4\n",
    "                dx, dy = DIRS[di]\n",
    "            i += dx\n",
    "            j += dy\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "DIRECTION = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        row = 0\n",
    "        col = -1\n",
    "        cur = 0\n",
    "        while head:\n",
    "            dr, dc = DIRECTION[cur]\n",
    "            row += dr\n",
    "            col += dc\n",
    "            if not (-1 < row < m and -1 < col < n and ans[row][col] == -1):\n",
    "                cur = (cur + 1) % 4\n",
    "                row -= dr\n",
    "                col -= dc\n",
    "                dr, dc = DIRECTION[cur]\n",
    "                row += dr\n",
    "                col += dc\n",
    "            ans[row][col] = head.val\n",
    "            head = head.next\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        i = j = di = 0\n",
    "        while head:\n",
    "            ans[i][j] = head.val\n",
    "            head = head.next\n",
    "            dx, dy = DIRS[di]\n",
    "            if not (0 <= i + dx < m and 0 <= j + dy < n and ans[i + dx][j + dy] == -1):\n",
    "                di = (di + 1) % 4\n",
    "                dx, dy = DIRS[di]\n",
    "            i += dx\n",
    "            j += dy\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        \n",
    "        ans = [[-1]*n for _ in range(m)]\n",
    "        ind = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        d=  x = y = 0\n",
    "        while head:\n",
    "            val  =head.val\n",
    "            head = head.next\n",
    "            ans[x][y] = val\n",
    "            a, b = ind[d]\n",
    "            if not (0<=x+a<m and 0<=y+b<n and ans[x+a][y+b]==-1):\n",
    "                d = (d+1)%4\n",
    "            a, b = ind[d]\n",
    "            x += a\n",
    "            y += b\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        i = j = di = 0\n",
    "        while head:\n",
    "            ans[i][j] = head.val\n",
    "            head = head.next\n",
    "            dx, dy = DIRS[di]\n",
    "            if not (0 <= i + dx < m and 0 <= j + dy < n and ans[i + dx][j + dy] == -1):\n",
    "                di = (di + 1) % 4\n",
    "                dx, dy = DIRS[di]\n",
    "            i += dx\n",
    "            j += dy\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/spiral-matrix-iv/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "from operator import le\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\r\n",
    "\r\n",
    "        matrix = []\r\n",
    "        for i in range(m):\r\n",
    "            matrix.append([0]*n)\r\n",
    "\r\n",
    "        target = m * n\r\n",
    "        cnt = 0\r\n",
    "\r\n",
    "        left, right = 0, n\r\n",
    "        up, down = 0, m\r\n",
    "\r\n",
    "        while True:\r\n",
    "            for i in range(left, right):\r\n",
    "                if head is not None:\r\n",
    "                    matrix[up][i] = head.val\r\n",
    "                    head = head.next\r\n",
    "                else:\r\n",
    "                    matrix[up][i] = -1\r\n",
    "                cnt += 1\r\n",
    "                if cnt == target:\r\n",
    "                    return matrix\r\n",
    "            up += 1\r\n",
    "\r\n",
    "            for i in range(up, down):\r\n",
    "                if head is not None:\r\n",
    "                    matrix[i][right-1] = head.val\r\n",
    "                    head = head.next\r\n",
    "                else:\r\n",
    "                    matrix[i][right-1] = -1\r\n",
    "                cnt += 1\r\n",
    "                if cnt == target:\r\n",
    "                    return matrix               \r\n",
    "            right -= 1\r\n",
    "\r\n",
    "            for i in range(right-1, left-1, -1):\r\n",
    "                if head is not None:\r\n",
    "                    matrix[down-1][i] = head.val\r\n",
    "                    head = head.next\r\n",
    "                else:\r\n",
    "                    matrix[down-1][i] = -1\r\n",
    "                cnt += 1\r\n",
    "                if cnt == target:\r\n",
    "                    return matrix\r\n",
    "            down -= 1\r\n",
    "\r\n",
    "            for i in range(down-1, up-1, -1):\r\n",
    "                if head is not None:\r\n",
    "                    matrix[i][left] = head.val\r\n",
    "                    head = head.next\r\n",
    "                else:\r\n",
    "                    matrix[i][left] = -1\r\n",
    "                cnt += 1\r\n",
    "                if cnt == target:\r\n",
    "                    return matrix\r\n",
    "            left += 1\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "DIRECTION = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        row = 0\n",
    "        col = -1\n",
    "        cur = 0\n",
    "        while head:\n",
    "            dr, dc = DIRECTION[cur]\n",
    "            row += dr\n",
    "            col += dc\n",
    "            if not (-1 < row < m and -1 < col < n and ans[row][col] == -1):\n",
    "                cur = (cur + 1) % 4\n",
    "                row -= dr\n",
    "                col -= dc\n",
    "                dr, dc = DIRECTION[cur]\n",
    "                row += dr\n",
    "                col += dc\n",
    "            ans[row][col] = head.val\n",
    "            head = head.next\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "DRIS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        i = j = di = 0\n",
    "        while head:\n",
    "            ans[i][j] = head.val\n",
    "            head = head.next\n",
    "            dx, dy = DRIS[di]\n",
    "            if not (0 <= i + dx < m and 0 <= j + dy < n and ans[i + dx][j + dy] == -1):\n",
    "                di = (di + 1) % 4\n",
    "                dx, dy = DRIS[di]\n",
    "            i += dx\n",
    "            j += dy\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "dir4 = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        i, j = 0, 0\n",
    "        d = 0\n",
    "        while head:\n",
    "            ans[i][j] = head.val\n",
    "            head = head.next\n",
    "            di, dj = dir4[d]\n",
    "            if not (0 <= i + di < m and 0 <= j + dj < n and ans[i+di][j+dj] == -1):\n",
    "                d = (d + 1) % 4\n",
    "                di, dj = dir4[d]\n",
    "            i += di\n",
    "            j += dj\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        mark = [[False] * n for _ in range(m)]\n",
    "        dir = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        i, j, pos, p = 0, 0, 1, head\n",
    "        while p:\n",
    "            ans[i][j] = p.val\n",
    "            mark[i][j] = True\n",
    "            xi, xj = i + dir[pos][0], j + dir[pos][1]\n",
    "            if xi < 0 or xi >= m or xj < 0 or xj >= n or mark[xi][xj]:\n",
    "                pos = (pos + 1) % 4\n",
    "            i, j = i + dir[pos][0], j + dir[pos][1]\n",
    "            p = p.next\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        def iter_(l,r,u,d):\n",
    "            while l <= r and u <= d:\n",
    "                for j in range(l, r+1):\n",
    "                    yield u, j\n",
    "                u += 1\n",
    "                for i in range(u, d+1):\n",
    "                    yield i, r\n",
    "                r -= 1\n",
    "                if u <= d:\n",
    "                    for j in range(r, l - 1, -1):\n",
    "                        yield d, j\n",
    "                d -= 1\n",
    "                if l <= r:\n",
    "                    for i in range(d, u - 1, -1):\n",
    "                        yield i, l\n",
    "                l += 1\n",
    "        ans = [[-1]*n for _ in range(m)]\n",
    "        for i, j in iter_(0, n-1, 0, m-1):\n",
    "            if not head:\n",
    "                break\n",
    "            ans[i][j] = head.val\n",
    "            head = head.next\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        mtx = [[-1] * n for _ in range(m)]\n",
    "        ds = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        d = 0\n",
    "        x = y = 0\n",
    "        while head:\n",
    "            mtx[x][y] = head.val\n",
    "            nx = x + ds[d][0]\n",
    "            ny = y + ds[d][1]\n",
    "            if not (0<=nx<m and 0<=ny<n) or mtx[nx][ny] != -1:\n",
    "                d = (d+1)%4\n",
    "            x += ds[d][0]\n",
    "            y += ds[d][1]\n",
    "            head = head.next\n",
    "        return mtx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "from operator import le\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\r\n",
    "\r\n",
    "        matrix = []\r\n",
    "        for i in range(m):\r\n",
    "            matrix.append([0]*n)\r\n",
    "\r\n",
    "        target = m * n\r\n",
    "        cnt = 0\r\n",
    "\r\n",
    "        left, right = 0, n\r\n",
    "        up, down = 0, m\r\n",
    "\r\n",
    "        while True:\r\n",
    "            for i in range(left, right):\r\n",
    "                if head:\r\n",
    "                    matrix[up][i] = head.val\r\n",
    "                    head = head.next\r\n",
    "                else:\r\n",
    "                    matrix[up][i] = -1\r\n",
    "                cnt += 1\r\n",
    "                if cnt == target:\r\n",
    "                    return matrix\r\n",
    "            up += 1\r\n",
    "\r\n",
    "            for i in range(up, down):\r\n",
    "                if head:\r\n",
    "                    matrix[i][right-1] = head.val\r\n",
    "                    head = head.next\r\n",
    "                else:\r\n",
    "                    matrix[i][right-1] = -1\r\n",
    "                cnt += 1\r\n",
    "                if cnt == target:\r\n",
    "                    return matrix               \r\n",
    "            right -= 1\r\n",
    "\r\n",
    "            for i in range(right-1, left-1, -1):\r\n",
    "                if head:\r\n",
    "                    matrix[down-1][i] = head.val\r\n",
    "                    head = head.next\r\n",
    "                else:\r\n",
    "                    matrix[down-1][i] = -1\r\n",
    "                cnt += 1\r\n",
    "                if cnt == target:\r\n",
    "                    return matrix\r\n",
    "            down -= 1\r\n",
    "\r\n",
    "            for i in range(down-1, up-1, -1):\r\n",
    "                if head:\r\n",
    "                    matrix[i][left] = head.val\r\n",
    "                    head = head.next\r\n",
    "                else:\r\n",
    "                    matrix[i][left] = -1\r\n",
    "                cnt += 1\r\n",
    "                if cnt == target:\r\n",
    "                    return matrix\r\n",
    "            left += 1\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        mark = [[False] * n for _ in range(m)]\n",
    "        dir = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        i, j, pos, p = 0, 0, 1, head\n",
    "        while p:\n",
    "            ans[i][j] = p.val\n",
    "            mark[i][j] = True\n",
    "            xi, xj = i + dir[pos][0], j + dir[pos][1]\n",
    "            if xi < 0 or xi >= m or xj < 0 or xj >= n or mark[xi][xj]:\n",
    "                pos = (pos + 1) % 4\n",
    "            i, j = i + dir[pos][0], j + dir[pos][1]\n",
    "            p = p.next\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        i = j = di = 0\n",
    "        while head:\n",
    "            ans[i][j] = head.val\n",
    "            head = head.next\n",
    "            dx, dy = DIRS[di]\n",
    "            if not (0 <= i + dx < m and 0 <= j + dy < n and ans[i + dx][j + dy] == -1):\n",
    "                di = (di + 1) % 4\n",
    "                dx, dy = DIRS[di]\n",
    "            i += dx\n",
    "            j += dy\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        s = [[-1]*n for _ in range(m)]\n",
    "        deltas = [[0, 1, n - 1], [1, 0, m - 1], [0, -1, 0], [-1, 0, 1]]\n",
    "        _dir = 0\n",
    "        dr, dc, limit = deltas[0]\n",
    "        row, cell = 0, -1\n",
    "        while head:\n",
    "            row += dr\n",
    "            cell += dc\n",
    "            s[row][cell] = head.val\n",
    "            head = head.next\n",
    "            if dr and row != limit or dc and cell != limit:\n",
    "                continue\n",
    "            if dr and row == limit:\n",
    "                deltas[_dir][2] -= dr\n",
    "            else:\n",
    "                deltas[_dir][2] -= dc\n",
    "            _dir = (_dir + 1) % 4\n",
    "            dr, dc, limit = deltas[_dir]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1]*n for _ in range(m)]\n",
    "        l, r, t, b, cur = 0, n-1, 0, m-1, head\n",
    "        while cur:\n",
    "            # top\n",
    "            for i in range(l, r+1):\n",
    "                if not cur:\n",
    "                    break\n",
    "                ans[t][i] = cur.val\n",
    "                cur = cur.next\n",
    "            t += 1\n",
    "            # right\n",
    "            for i in range(t, b+1):\n",
    "                if not cur:\n",
    "                    break\n",
    "                ans[i][r] = cur.val\n",
    "                cur = cur.next\n",
    "            r -= 1\n",
    "            # botton\n",
    "            for i in range(r, l-1, -1):\n",
    "                if not cur:\n",
    "                    break\n",
    "                ans[b][i] = cur.val\n",
    "                cur = cur.next\n",
    "            b -= 1\n",
    "            # left\n",
    "            for i in range(b, t-1, -1):\n",
    "                if not cur:\n",
    "                    break\n",
    "                ans[i][l] = cur.val\n",
    "                cur = cur.next\n",
    "            l += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        list1 = [-1]*n\n",
    "        matrix = []\n",
    "        for i in range(m):\n",
    "            matrix.append(list(list1))\n",
    "        l,r,h,d = 0,n-1,0,m-1\n",
    "        while head:\n",
    "            for i in range(l,r+1):\n",
    "                if head:\n",
    "                    matrix[h][i] = head.val\n",
    "                    head = head.next\n",
    "                \n",
    "            h+=1\n",
    "            for i in range(h,d+1):\n",
    "                if head:\n",
    "                    matrix[i][r] = head.val\n",
    "                    head = head.next\n",
    "                \n",
    "            r-=1\n",
    "            for i in range(r,l-1,-1):\n",
    "                if head:\n",
    "                    matrix[d][i] = head.val\n",
    "                    head = head.next\n",
    "                \n",
    "            d-=1\n",
    "            for i in range(d,h-1,-1):\n",
    "                if head:\n",
    "                    matrix[i][l] = head.val\n",
    "                    head = head.next\n",
    "            l+=1\n",
    "        return matrix\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "\n",
    "        i = j = di = 0\n",
    "\n",
    "        while head:\n",
    "\n",
    "            ans[i][j] = head.val\n",
    "\n",
    "            head = head.next\n",
    "\n",
    "            dx, dy = DIRS[di]\n",
    "\n",
    "            if not (0 <= i + dx < m and 0 <= j + dy < n and ans[i + dx][j + dy] == -1):\n",
    "\n",
    "                di = (di + 1) % 4\n",
    "\n",
    "                dx, dy = DIRS[di]\n",
    "\n",
    "            i += dx\n",
    "\n",
    "            j += dy\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        g = [[-1] * n for _ in range(m)]\n",
    "        d = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        cur = 0\n",
    "        i = j = 0\n",
    "        while head:\n",
    "            g[i][j] = head.val\n",
    "            r, c = i+d[cur][0], j+d[cur][1]\n",
    "            if 0<=r<m and 0<=c<n and g[r][c] == -1:\n",
    "                i, j = r, c \n",
    "            else:\n",
    "                cur = (cur + 1) % 4\n",
    "                i, j = i+d[cur][0], j+d[cur][1]\n",
    "            head = head.next\n",
    "        return g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        res = [[-1] * n for _ in range(m)]\n",
    "        i = j = 0\n",
    "        directions = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        idx = 0\n",
    "        while head:\n",
    "            res[i][j] = head.val\n",
    "            head = head.next\n",
    "            new_i, new_j = i+directions[idx][0], j+directions[idx][1]\n",
    "            if new_i < 0 or new_i >= m or new_j < 0 or new_j >= n or res[new_i][new_j] != -1:\n",
    "                idx = (idx+1) % 4\n",
    "            i, j = i+directions[idx][0], j+directions[idx][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        l, r, t, b = 0, n - 1, 0, m - 1\n",
    "        mat = [[-1] * n for _ in range(m)]\n",
    "        num, tar = 1, m * n\n",
    "        while head:\n",
    "            for i in range(l, r + 1):  \n",
    "                if head:  # Add condition here\n",
    "                    mat[t][i] = head.val\n",
    "                    head = head.next\n",
    "                else:\n",
    "                    break\n",
    "            t += 1\n",
    "            for i in range(t, b + 1):  \n",
    "                if head:  # And here\n",
    "                    mat[i][r] = head.val\n",
    "                    head = head.next\n",
    "                else:\n",
    "                    break\n",
    "            r -= 1\n",
    "            for i in range(r, l - 1, -1):\n",
    "                if head:  # And here\n",
    "                    mat[b][i] = head.val\n",
    "                    head = head.next\n",
    "                else:\n",
    "                    break\n",
    "            b -= 1\n",
    "            for i in range(b, t - 1, -1): # bottom to top\n",
    "                if head:  # And here\n",
    "                    mat[i][l] = head.val\n",
    "                    head = head.next\n",
    "                else:\n",
    "                    break\n",
    "            l += 1\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        cur = head\n",
    "        dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        idx = 0\n",
    "        x, y = 0, 0\n",
    "        while cur:\n",
    "            v = cur.val\n",
    "            cur = cur.next\n",
    "            ans[x][y] = v\n",
    "            while cur:\n",
    "                dx, dy = dir[idx]\n",
    "                a, b = x + dx, y + dy\n",
    "                if 0 <= a < m and 0 <= b < n and ans[a][b] == -1:\n",
    "                    x, y = a, b\n",
    "                    break\n",
    "                else:\n",
    "                    idx = (idx + 1) % 4\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        i = j = di = 0\n",
    "        while head:\n",
    "            ans[i][j] = head.val\n",
    "            head = head.next\n",
    "            dx, dy = DIRS[di]\n",
    "            if not (0 <= i + dx < m and 0 <= j + dy < n and ans[i + dx][j + dy] == -1):\n",
    "                di = (di + 1) % 4\n",
    "                dx, dy = DIRS[di]\n",
    "            i += dx\n",
    "            j += dy\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        i = j = di = 0\n",
    "        while head:\n",
    "            ans[i][j] = head.val\n",
    "            head = head.next\n",
    "            dx, dy = DIRS[di]\n",
    "            if not (0 <= i + dx < m and 0 <= j + dy < n and ans[i + dx][j + dy] == -1):\n",
    "                di = (di + 1) % 4\n",
    "                dx, dy = DIRS[di]\n",
    "            i += dx\n",
    "            j += dy\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        res = [[-1] * n for _ in range(m)]\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        res[0][0] = head.val\n",
    "        head = head.next\n",
    "        visited[0][0] = 1\n",
    "        directs = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        i, j =0, 0\n",
    "\n",
    "        while head:\n",
    "            for d in directs:\n",
    "                while 0 <= i + d[0] < m and 0 <= j + d[1] < n and visited[i + d[0]][j + d[1]] != 1:\n",
    "                    i, j = i + d[0], j + d[1]\n",
    "                    visited[i][j] = 1\n",
    "                    if head:\n",
    "                        res[i][j] = head.val\n",
    "                        head = head.next\n",
    "                    else:\n",
    "                        break\n",
    "                \n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1] * n for _ in range(m)]\n",
    "        i = j = di = 0\n",
    "        while head:\n",
    "            ans[i][j] = head.val\n",
    "            head = head.next\n",
    "            dx, dy = DIRS[di]\n",
    "            if not (0 <= i + dx < m and 0 <= j + dy < n and ans[i + dx][j + dy] == -1):\n",
    "                di = (di + 1) % 4\n",
    "                dx, dy = DIRS[di]\n",
    "            i += dx\n",
    "            j += dy\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "class Solution:\r\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\r\n",
    "        ans = [[-1] * n for _ in range(m)]\r\n",
    "        if not head:\r\n",
    "            return ans\r\n",
    "        ans[0][0] = head.val\r\n",
    "        head = head.next\r\n",
    "        i, j = 0, 0\r\n",
    "        while head:\r\n",
    "            # 到达右边界,且不可往上走\r\n",
    "            if j + 1 < n and ans[i][j + 1] == -1 and (i - 1 < 0 or ans[i - 1][j] != -1):\r\n",
    "                j += 1\r\n",
    "            # 到达下边界,且不可往左走\r\n",
    "            elif i + 1 < m and ans[i + 1][j] == -1 and (j + 1 >= n or ans[i][j + 1] != -1):\r\n",
    "                i += 1\r\n",
    "            # 到达左边界,且不可往下走\r\n",
    "            elif j - 1 >= 0 and ans[i][j - 1] == -1 and (i + 1 >= m or ans[i + 1][j] != -1):\r\n",
    "                j -= 1\r\n",
    "            # 到达上边界,且不可往右走\r\n",
    "            elif i - 1 >= 0 and ans[i - 1][j] == -1 and (j - 1 < 0 or ans[i][j - 1] != -1):\r\n",
    "                i -= 1\r\n",
    "            ans[i][j] = head.val\r\n",
    "            head = head.next\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "class Solution:\r\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\r\n",
    "        ans = [[-1] * n for _ in range(m)]\r\n",
    "        if not head:\r\n",
    "            return ans\r\n",
    "        ans[0][0] = head.val\r\n",
    "        head = head.next\r\n",
    "        i, j = 0, 0\r\n",
    "        while head:\r\n",
    "            # 到达右边界\r\n",
    "            if j + 1 < n and ans[i][j + 1] == -1 and (i - 1 < 0 or ans[i - 1][j] != -1):\r\n",
    "                j += 1\r\n",
    "            # 到达下边界\r\n",
    "            elif i + 1 < m and ans[i + 1][j] == -1 and (j + 1 >= n or ans[i][j + 1] != -1):\r\n",
    "                i += 1\r\n",
    "            # 到达左边界\r\n",
    "            elif j - 1 >= 0 and ans[i][j - 1] == -1 and (i + 1 >= m or ans[i + 1][j] != -1):\r\n",
    "                j -= 1\r\n",
    "            # 到达上边界\r\n",
    "            elif i - 1 >= 0 and ans[i - 1][j] == -1 and (j - 1 < 0 or ans[i][j - 1] != -1):\r\n",
    "                i -= 1\r\n",
    "            ans[i][j] = head.val\r\n",
    "            head = head.next\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        list1 = [-1]*n\n",
    "        matrix = []\n",
    "        for i in range(m):\n",
    "            matrix.append(list(list1))\n",
    "        l,r,h,d = 0,n-1,0,m-1\n",
    "        while head:\n",
    "            for i in range(l,r+1):\n",
    "                if head:\n",
    "                    matrix[h][i] = head.val\n",
    "                    head = head.next\n",
    "                else:\n",
    "                    break\n",
    "            h+=1\n",
    "            for i in range(h,d+1):\n",
    "                if head:\n",
    "                    matrix[i][r] = head.val\n",
    "                    head = head.next\n",
    "                else:\n",
    "                    break\n",
    "            r-=1\n",
    "            for i in range(r,l-1,-1):\n",
    "                if head:\n",
    "                    matrix[d][i] = head.val\n",
    "                    head = head.next\n",
    "                else:\n",
    "                    break\n",
    "            d-=1\n",
    "            for i in range(d,h-1,-1):\n",
    "                if head:\n",
    "                    matrix[i][l] = head.val\n",
    "                    head = head.next\n",
    "                else:\n",
    "                    break\n",
    "            l+=1\n",
    "        return matrix\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        matrix = [[-1]*n for _ in range(m)]\n",
    "        cur = head\n",
    "        # Define border\n",
    "        left, right, upper, bottom = 0, n-1, 0, m-1\n",
    "        while cur:\n",
    "            for l in range(left, right+1, 1):\n",
    "                if cur:\n",
    "                    matrix[upper][l] = cur.val\n",
    "                    cur = cur.next\n",
    "            upper += 1\n",
    "            for t in range(upper, bottom+1, 1):\n",
    "                if cur:\n",
    "                    matrix[t][right] = cur.val\n",
    "                    cur = cur.next\n",
    "            right -= 1\n",
    "            for r in range(right, left-1, -1):\n",
    "                if cur:\n",
    "                    matrix[bottom][r] = cur.val\n",
    "                    cur = cur.next\n",
    "            bottom -= 1\n",
    "            for b in range(bottom, upper-1, -1):\n",
    "                if cur:\n",
    "                    matrix[b][left] = cur.val\n",
    "                    cur = cur.next\n",
    "            left += 1\n",
    "        return matrix\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        matrix = [[-1]*n for _ in range(m)]\n",
    "        cur = head\n",
    "        # Define border\n",
    "        left, right, upper, bottom = 0, n-1, 1, m-1\n",
    "        # Define direction\n",
    "        around = [(0,1), (1,0),(0,-1),(-1,0)]\n",
    "\n",
    "        x,y, Dir = 0,0,0\n",
    "        while cur:\n",
    "            if x>=0 and x<m and y>=0 and y<n:\n",
    "                matrix[x][y] = cur.val\n",
    "            if Dir==0 and y==right:\n",
    "                Dir += 1\n",
    "                right -=1\n",
    "            elif Dir==1 and x==bottom:\n",
    "                Dir += 1\n",
    "                bottom -= 1\n",
    "            elif Dir == 2 and y==left:\n",
    "                Dir += 1\n",
    "                left += 1\n",
    "            elif Dir == 3 and x==upper:\n",
    "                Dir = 0\n",
    "                upper += 1\n",
    "            \n",
    "            x += around[Dir][0]\n",
    "            y += around[Dir][1]\n",
    "            cur = cur.next\n",
    "\n",
    "        return matrix\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        matrix = [[-1]*n for _ in range(m)]\n",
    "        cur = head\n",
    "        # Define border\n",
    "        left, right, upper, bottom = 0, n-1, 1, m-1\n",
    "        # Define direction\n",
    "        around = [(0,1), (1,0),(0,-1),(-1,0)]\n",
    "\n",
    "        x,y, Dir = 0,0,0\n",
    "        while cur:\n",
    "            if x>=0 and x<m and y>=0 and y<n:\n",
    "                matrix[x][y] = cur.val\n",
    "            if Dir==0 and y==right:\n",
    "                Dir += 1\n",
    "                right -=1\n",
    "            elif Dir==1 and x==bottom:\n",
    "                Dir += 1\n",
    "                bottom -= 1\n",
    "            elif Dir == 2 and y==left:\n",
    "                Dir += 1\n",
    "                left += 1\n",
    "            elif Dir == 3 and x==upper:\n",
    "                print(cur.val)\n",
    "                print(x,y)\n",
    "                Dir = 0\n",
    "                upper += 1\n",
    "            \n",
    "            x += around[Dir][0]\n",
    "            y += around[Dir][1]\n",
    "            cur = cur.next\n",
    "\n",
    "        return matrix\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        res = []\n",
    "        while head:\n",
    "            res.append(head.val)\n",
    "            head = head.next\n",
    "        matrix = [[-1]*n for _ in range(m)]\n",
    "        visited = [[False]*n for _ in range(m)]\n",
    "        x, y, dirrection_index = 0,0,0\n",
    "        directions = [(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        for i in range(m*n):\n",
    "            if i < len(res):\n",
    "                matrix[x][y] = res[i]\n",
    "            visited[x][y] = True\n",
    "            next_x = x + directions[dirrection_index%4][0]\n",
    "            next_y = y + directions[dirrection_index%4][1]\n",
    "            if next_x<0 or next_x>=m or next_y<0 or next_y>=n or visited[next_x][next_y]:\n",
    "                dirrection_index = dirrection_index + 1\n",
    "                next_x = x + directions[dirrection_index%4][0]\n",
    "                next_y = y + directions[dirrection_index%4][1]\n",
    "            x, y = next_x, next_y\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        result = [[-1]*n for _ in range(m)]\n",
    "        cur = head\n",
    "        direction = 0\n",
    "        x, y = 0, 0\n",
    "        offset = 0\n",
    "        while(cur):\n",
    "            result[x][y] = cur.val\n",
    "            cur = cur.next\n",
    "            if(direction == 0):\n",
    "                if(y == n - 1 - offset):\n",
    "                    x = x + 1\n",
    "                    direction = 1\n",
    "                else:\n",
    "                    y = y + 1\n",
    "            elif(direction == 1):\n",
    "                if(x == m - 1 - offset):\n",
    "                    y = y - 1\n",
    "                    direction = 2\n",
    "                else:\n",
    "                    x = x + 1\n",
    "            elif(direction == 2):\n",
    "                if(y == offset):\n",
    "                    x = x - 1\n",
    "                    direction = 3\n",
    "                    offset += 1\n",
    "                else:\n",
    "                    y = y - 1\n",
    "            else:\n",
    "                if(x == offset):\n",
    "                    y = y + 1\n",
    "                    direction = 0\n",
    "                else:\n",
    "                    x = x - 1\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def spiralMatrix(self, m, n, head):\n",
    "        lst_ans = [[-1] * n for _ in range(m)]\n",
    "        m_top, m_bottom, n_left, n_right, i, j, direction = 0, m - 1, 0, n - 1, 0, 0, 1\n",
    "        while head:\n",
    "            lst_ans[i][j] = head.val\n",
    "            head = head.next\n",
    "            if direction == 1:\n",
    "                if j < n_right: \n",
    "                    j += 1\n",
    "                    continue\n",
    "                else:          \n",
    "                    direction = 2\n",
    "                    m_top += 1\n",
    "            if direction == 2:\n",
    "                if i < m_bottom:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                else:           \n",
    "                    direction = 3\n",
    "                    n_right -= 1\n",
    "            if direction == 3:\n",
    "                if j > n_left:\n",
    "                    j -= 1\n",
    "                    continue\n",
    "                else:           \n",
    "                    direction = 4\n",
    "                    m_bottom -= 1\n",
    "            if direction == 4:\n",
    "                if i > m_top:\n",
    "                    i -= 1\n",
    "                    continue\n",
    "                else:           \n",
    "                    direction = 1\n",
    "                    n_left += 1\n",
    "            if direction == 1:\n",
    "                if j < n_right: \n",
    "                    j += 1\n",
    "                    continue\n",
    "                else:          \n",
    "                    direction = 2\n",
    "                    m_top += 1\n",
    "        return lst_ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "\n",
    "        result = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        x, y = 0, 0\n",
    "        p = 0\n",
    "\n",
    "        node = head\n",
    "        while node is not None:\n",
    "\n",
    "            result[x][y] = node.val\n",
    "            dx, dy = direction[p]\n",
    "\n",
    "            if (x + dx) < 0 or (x + dx) >= m or (y + dy) < 0 or (y + dy) >= n or result[x + dx][y + dy] != -1:\n",
    "                p = (p + 1) % 4\n",
    "            \n",
    "            dx, dy = direction[p]\n",
    "            x, y = x + dx, y + dy\n",
    "\n",
    "            node = node.next\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        result = [[-1 for i in range(n)] for _ in range(m)]\n",
    "        direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        i, j = 0, 0\n",
    "        k = 0\n",
    "        while head:\n",
    "            if 0 <= i < m and 0 <= j < n and result[i][j] == -1:\n",
    "                result[i][j] = head.val\n",
    "                head = head.next\n",
    "            else:\n",
    "                i -= direction[k % 4][0]\n",
    "                j -= direction[k % 4][1]\n",
    "                k += 1\n",
    "            i += direction[k % 4][0]\n",
    "            j += direction[k % 4][1]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        res = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "        l, r, t, b = 0, n - 1, 0, m - 1\n",
    "        node = head\n",
    "        flag = False\n",
    "\n",
    "        while node:\n",
    "            for i in range(l, r + 1):\n",
    "                res[t][i] = node.val\n",
    "                if node.next: node = node.next\n",
    "                else: \n",
    "                    flag = True\n",
    "                    break\n",
    "            if flag: break\n",
    "            t += 1\n",
    "            for i in range(t, b + 1):\n",
    "                res[i][r] = node.val\n",
    "                if node.next: node = node.next\n",
    "                else: \n",
    "                    flag = True\n",
    "                    break\n",
    "            if flag: break\n",
    "            r -= 1\n",
    "            for i in range(r, l - 1, -1):\n",
    "                res[b][i] = node.val\n",
    "                if node.next: node = node.next\n",
    "                else:\n",
    "                    flag = True\n",
    "                    break\n",
    "            if flag: break\n",
    "            b -= 1\n",
    "            for i in range(b, t - 1, -1):\n",
    "                res[i][l] = node.val\n",
    "                if node.next: node = node.next\n",
    "                else:\n",
    "                    flag = True\n",
    "                    break\n",
    "            if flag: break\n",
    "            l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        l, r, t, b = 0, n - 1, 0, m - 1\n",
    "        mat = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "        while head:\n",
    "            # from left to right\n",
    "            for i in range(l, r + 1):\n",
    "                if head:\n",
    "                    mat[t][i] = head.val\n",
    "                    head = head.next\n",
    "            t += 1\n",
    "            # from top to buttom\n",
    "            for i in range(t, b + 1):\n",
    "                if head:\n",
    "                    mat[i][r] = head.val\n",
    "                    head = head.next\n",
    "            r -= 1\n",
    "            # from right to left\n",
    "            for i in range(r, l - 1, -1):\n",
    "                if head:\n",
    "                    mat[b][i] = head.val\n",
    "                    head = head.next\n",
    "            b -= 1\n",
    "            # from buttom to top\n",
    "            for i in range(b, t - 1, -1):\n",
    "                if head:\n",
    "                    mat[i][l] = head.val\n",
    "                    head = head.next\n",
    "            l += 1\n",
    "\n",
    "\n",
    "        return mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        l, r, t, b = 0, n - 1, 0, m - 1\n",
    "        mat = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "        while head:\n",
    "            # from left to right\n",
    "            for i in range(l, r + 1):\n",
    "                if head:\n",
    "                    mat[t][i] = head.val\n",
    "                    head = head.next\n",
    "            t += 1\n",
    "            # from top to buttom\n",
    "            for i in range(t, b + 1):\n",
    "                if head:\n",
    "                    mat[i][r] = head.val\n",
    "                    head = head.next\n",
    "            r -= 1\n",
    "            # from right to left\n",
    "            for i in range(r, l - 1, -1):\n",
    "                if head:\n",
    "                    mat[b][i] = head.val\n",
    "                    head = head.next\n",
    "            b -= 1\n",
    "            # from buttom to top\n",
    "            for i in range(b, t - 1, -1):\n",
    "                if head:\n",
    "                    mat[i][l] = head.val\n",
    "                    head = head.next\n",
    "            l += 1\n",
    "\n",
    "\n",
    "        return mat\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        matrix = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "        left, right = 0, n - 1 # 行\n",
    "        low, high = 0, m - 1 # 列\n",
    "        i = 1\n",
    "        while head:\n",
    "            if i % 4 == 1:\n",
    "                for j in range(left, right + 1):\n",
    "                    if head:\n",
    "                        matrix[low][j] = head.val\n",
    "                        head = head.next\n",
    "                low += 1\n",
    "                i += 1\n",
    "                \n",
    "            elif i % 4 == 2:\n",
    "                for j in range(low, high + 1):\n",
    "                    if head:\n",
    "                        matrix[j][right] = head.val\n",
    "                        head = head.next\n",
    "                right -= 1\n",
    "                i += 1\n",
    "            elif i % 4 == 3:\n",
    "                for j in range(right, left - 1, -1):\n",
    "                    if head:\n",
    "                        matrix[high][j] = head.val\n",
    "                        head = head.next\n",
    "                high -= 1\n",
    "                i += 1\n",
    "            elif i % 4 == 0:\n",
    "                for j in range(high, low - 1, -1):\n",
    "                    if head:\n",
    "                        matrix[j][left] = head.val\n",
    "                        head = head.next\n",
    "                left += 1\n",
    "                i += 1 \n",
    "        return matrix "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        ans = [[-1 for i in range(n)] for k in range(m)]\n",
    "        l, r, u, d = -1, n, -1, m\n",
    "        x, y = 0, 0\n",
    "        while head:\n",
    "            while head and x < r:\n",
    "                ans[y][x] = head.val\n",
    "                x, head = x+1, head.next\n",
    "            x, u, y = x-1, u+1, y+1\n",
    "            while head and y < d:\n",
    "                ans[y][x] = head.val\n",
    "                y, head = y+1, head.next\n",
    "            y, r, x = y-1, r-1, x-1\n",
    "            while head and x > l:\n",
    "                ans[y][x] = head.val\n",
    "                x, head = x-1, head.next\n",
    "            x, d, y = x+1, d-1, y-1\n",
    "            while head and y > u:\n",
    "                ans[y][x] = head.val\n",
    "                y, head = y-1, head.next\n",
    "            y, l, x = y+1, l+1, x+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        res = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "        isFilled = [[False for _ in range(n)] for _ in range(m)]\n",
    "        i, j = 0, 0\n",
    "        directionX, directionY = 0, 1\n",
    "        while head:\n",
    "            res[i][j] = head.val\n",
    "            head = head.next\n",
    "            isFilled[i][j] = True\n",
    "            if not (0 <= i+directionX < m and 0 <= j+directionY < n and not isFilled[i+directionX][j+directionY]):\n",
    "                directionX, directionY = directionY, -directionX\n",
    "            i += directionX\n",
    "            j += directionY\n",
    "            if not (0 <= i < m and 0 <= j < n and not isFilled[i][j]):\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:\n",
    "        res = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "        isFilled = [[False for _ in range(n)] for _ in range(m)]\n",
    "        i, j = 0, 0\n",
    "        directionX, directionY = 0, 1\n",
    "        while head:\n",
    "            res[i][j] = head.val\n",
    "            head = head.next\n",
    "            isFilled[i][j] = True\n",
    "            if not (0 <= i+directionX < m and 0 <= j+directionY < n and not isFilled[i+directionX][j+directionY]):\n",
    "                directionX, directionY = directionY, -directionX\n",
    "            i += directionX\n",
    "            j += directionY\n",
    "            if not (0 <= i < m and 0 <= j < n and not isFilled[i][j]):\n",
    "                break\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
